Tweet
Login
Mathematics Crystal
You may switch between
tex
and
pdf
by changing the end of the URL.
Home
About Us
Materials
Site Map
Questions and Answers
Skills
Topic Notes
HSC
Integration
Others
Tangent
UBC
UNSW
Calculus Advanced
Challenges
Complex Numbers
Conics
Differentiation
Integration
Linear Algebra
Mathematical Induction
Motion
Others
Polynomial Functions
Probability
Sequences and Series
Trigonometry
/
Topics /
Mathematical Induction /
MI Inequalities.tex
--Quick Links--
The Number Empire
Wolfram Mathematica online integrator
FooPlot
Calc Matthen
Walter Zorn
Quick Math
Lists of integrals
List of integrals of trigonometric functions
PDF
\documentclass[10pt]{article} \usepackage{amssymb,amsmath} \usepackage[hmargin=1cm,vmargin=1cm]{geometry} \begin{document} {\large Mathematical Induction \--- Inequalities} \begin{align*} \text{Example}\quad P(n):\quad&2^n>n\quad\text{for all integers $n\geq 0$ .}\\ P(0):\quad&2^0=1>0\:,\quad\therefore P(0)\text{ is true.}\\ P(1):\quad&2^1=2>1\:,\quad\therefore P(1)\text{ is true.}\\ \text{If $P(k)$ is }&\text{true up to some integer }k\geq 1\text{ , then } 2^k>k\\ P(k+1):\quad&2^{k+1}=2\cdot 2^k>2k=k+k\geq k+1\:,\quad\therefore 2^{k+1}>k+1\\ \therefore\quad&\text{By the PMI, $P(n)$ is true for all integers $n\geq 0$ .}\\ \\ \text{Similarly}\quad P(n):\quad&2^n>n^2\quad\text{for all integers $n\geq 5$ .}\\ P(5):\quad&2^5=32>5^2=25\:,\quad\therefore P(5)\text{ is true.}\\ P(k):\quad&2^k>k^2\:,\quad\text{for }k\geq 5\\ P(k+1):\quad&2^{k+1}=2\cdot 2^k>2k^2\\ =&\:k^2+k\cdot k\geq k^2+5k\\ =&\:k^2+2k+3k>k^2+2k+1\\ =&\:(k+1)^2\:,\quad\therefore 2^{k+1}>(k+1)^2\\ \\ P(n):\quad&2^n>n^3\quad\text{for all integers $n\geq 10$ .}\\ P(10):\quad&2^{10}=1024>10^3=1000\:,\quad\therefore P(10)\text{ is true.}\\ P(k):\quad&2^k>k^3\:,\quad\text{for }k\geq 10\\ P(k+1):\quad&2^{k+1}=2\cdot 2^k>2k^3\\ =&\:k^3+k\cdot k^2\geq k^3+10k^2\\ =&\:k^3+3k^2+7k^2>k^3+3k^2+7k\cdot 10\\ =&\:k^3+3k^2+3k+67k>k^3+3k^2+3k+1\\ =&\:(k+1)^3\:,\quad\therefore 2^{k+1}>(k+1)^3\\ \\ \text{Aternatively}\quad P(n):\quad&2^n>n^4\quad\text{for all integers $n\geq 17$ .}\\ P(17):\quad&2^{17}=131072>17^4=83521\:,\quad\therefore P(17)\text{ is true.}\\ P(k):\quad&2^k>k^4\:,\quad\text{for }k\geq 17\\ \text{i.e. }&2^k-k^4>0\\ P(k+1):\quad&2^{k+1}-(k+1)^4\\ =&\:2\cdot 2^k-k^4-4k^3-6k^2-4k-1>2\cdot k^4-k^4-4k^3-6k^2-4k-1\\ =&\:k^4-4k^3-6k^2-4k-1\\ \geq&\:17\cdot(k^3-4k^2-6k-4)-1\\ \geq&\:17\cdot[17\cdot(k^2-4k-6)-4]-1\\ \geq&\:17\cdot[17\cdot\big(17\cdot(k-4)-6\big)-4]-1\\ \geq&\:17\cdot[17\cdot\big(17\cdot(17-4)-6\big)-4]-1>0\:,\quad\therefore 2^{k+1}>(k+1)^4\\ \end{align*} \begin{align*} \text{Example}\quad P(n):\quad&3^n>2n+5\quad\text{for all integers $n\geq 3$ .}\\ P(3):\quad&3^3=27>2\cdot 3+5=11\:,\quad\therefore P(3)\text{ is true.}\\ \text{If $P(k)$ is }&\text{true up to some integer }k\geq 3\text{ , then } 3^k>2k+5\\ P(k+1):\quad&3^{k+1}=3\cdot 3^k>3\cdot(2k+5)\\ =&\:6k+15>2k+7\\ =&\:2(k+1)+5\:,\quad\therefore 3^{k+1}>2(k+1)+5\\ \therefore\quad&\text{By the PMI, $P(n)$ is true for all integers $n\geq 3$ .}\\ \\ \text{Example}\quad P(n):\quad&n!\geq 2^{n-1}\quad\text{for all integers $n\geq 1$ .}\\ P(1):\quad&1!=1\geq 2^{1-1}=1\:,\quad\therefore P(1)\text{ is true.}\\ \text{If $P(k)$ is }&\text{true up to some integer }k\geq 1\text{ , then } k!\geq 2^{k-1}\\ P(k+1):\quad&(k+1)!=(k+1)k!\geq(k+1)2^{k-1}\geq 2\cdot 2^{k-1}=2^{(k+1)-1}\\ \therefore\quad&\text{By the PMI, $P(n)$ is true for all integers $n\geq 1$ .}\\ \\ \text{Example a)}\quad\qquad&\text{If $a_1>1$ and $a_2>1$, then }a_1 a_2-a_1-a_2+1>0\\ \text{Proof:}\quad&a_1-1>0\:,\quad a_2-1>0\:,\quad(a_1-1)(a_2-1)>0\\ \therefore\quad&a_1 a_2-a_1-a_2+1>0\\ \text{b)}\quad P(n):\quad&\prod_{r=1}^n a_r>\sum_{r=1}^n a_r+1-n\quad\text{for all integers $n\geq 2$, where $a_r>1$ .}\\ \text{Let}\quad&P_n=\prod_{r=1}^n a_r\:,\quad\text{and}\quad S_n=\sum_{r=1}^n a_r\\ P(n):\quad&P_n>S_n+1-n\\ P(2):\quad&\text{from a)}\quad a_1 a_2>a_1+a_2+1-2>0\\ &\text{i.e. }P_2>S_2+1-2\:,\quad\therefore P(1)\text{ is true.}\\ \text{If $P(k)$ is }&\text{true up to some integer }k\geq 2\text{ , then } P_k>S_k+1-k\\ %\text{or}\quad&P_k-S_k-1+k>0\\ P(k+1):\quad&P_{k+1}-S_{k+1}-1+(k+1)\\ =&\:a_{k+1}P_k-a_{k+1}-S_k-1+k+1\\ =&\:a_{k+1}(S_k+1-k)-a_{k+1}-S_k+k\\ =&\:a_{k+1}S_k+\rlap{------}a_{k+1}-a_{k+1}k-\rlap{------}a_{k+1}-S_k+k\\ =&\:(a_{k+1}-1)(S_k-k)\\ =&\left(a_{k+1}-1\right)\left(\sum_{r=1}^k a_r-\sum_{r=1}^k 1\right)\\ =&\left(a_{k+1}-1\right)\sum_{r=1}^n\left(a_r-1\right)>0\:,\quad\therefore P_{k+1}>S_{k+1}+1-(k+1)\\ \therefore\quad&\text{By the PMI, $P(n)$ is true for all integers $n\geq 2$ .}\\ \end{align*} \end{document}